//给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。 
//
// 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。 
//
// 你可以按任意顺序返回答案。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [2,7,11,15], target = 9
//输出：[0,1]
//解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
// 
//
// 示例 2： 
//
// 
//输入：nums = [3,2,4], target = 6
//输出：[1,2]
// 
//
// 示例 3： 
//
// 
//输入：nums = [3,3], target = 6
//输出：[0,1]
// 
//
// 
//
// 提示： 
//
// 
// 2 <= nums.length <= 104 
// -109 <= nums[i] <= 109 
// -109 <= target <= 109 
// 只会存在一个有效答案 
// 
//
// 进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？ 
// Related Topics 数组 哈希表 
// 👍 11427 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] res = new int[2];
        //建立index数组
        List<Integer> ind = new ArrayList<>(nums.length);
//        System.out.println("ind.size..."+ind.size());
        for(int i=0; i<nums.length; i++){//注意不能取ind的size，此时它还为0
//            ind.set(i,i);
            ind.add(i);
        }
        //对建立的index数组，按nums值进行排序，得到一个index数组
        //按这个数组，从nums里拿，就是有序的结果，从小到大
//        System.out.println(ind);
        ind.sort((Integer left, Integer right)->{
            return nums[left] - nums[right] ;
        });
//        System.out.println(ind);

        //从头遍历元素记为x，并从后半部分通过二分查找找到目标值(target-x)
        //0,1,2   ==> mid = 1
        //0,1,2,3 ==> mid = 1
        //注意不能到一半就不遍历了，因为有可能是最后两个进行组合呢
        for(int i=0; i<(ind.size()-1); i++){
            int x = nums[ind.get(i)];
            int remain = target - x;
//            System.out.println("i:\t"+i+"\t,x:\t"+x+"\t,remain:\t"+remain);
            //二分查找后半部分
            int from = i+1;
            int right = binarySearcn(ind,nums,from,remain);
            if(-1!=right){
                res[0] = ind.get(i);
                res[1] = ind.get(right);
                return res;
            }
        }
        res[0]=-1;
        res[1]=-1;
        return res;
    }
    public int binarySearcn(List<Integer> ind, int[] nums, int from, int target){
        int head = from, tail=nums.length - 1, mid;
        while(tail - head > 3){
            mid = head + ((tail - head) >> 1);
            int midVal = nums[ind.get(mid)];
            if(midVal == target){
                return mid;
            }
            else if( midVal > target){
                tail = mid - 1;
            }else {
                head = mid + 1;
            }
        }
        for(int i=head; i<=tail; i++){
            if(nums[ind.get(i)] == target){
                return i;
            }
        }
        return -1;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
